# 作者: 陈其志 
# 2025年02月24日10时31分17秒 
# 2716847110@qq.com

class Node:
    def __init__(self, value=0, lchild=None, rchild=None):
        self.value = value
        self.lchild = lchild
        self.rchild = rchild


class Tree:
    def __init__(self, ):
        self.root = None
        self.queue = []

    def build_tree(self, value):
        """
        层次建树（完全二叉树），需要使用到辅助队列：每进来一个节点都把他放到辅助队列
        每次入队一个节点，判断根节点是否为空，若为空，则作为根节点
        若不为空，判断队头元素的左孩子是否为空，若为空，则作为左孩子
        若不为空，判断队头元素的右孩子是否为空，若为空，则作为右孩子，并出队
        :param value:
        :return:
        """
        # 每新进来一个元素就新实例化一个节点
        new_node = Node(value)
        # 新节点入辅助队列
        self.queue.append(new_node)
        # 层次建树，先判断根节点
        if self.root is None:
            # 若根节点为空则最先入队的元素作为根节点
            self.root = new_node
        else:
            # 判断队头元素是否有左孩子
            if self.queue[0].lchild is None:
                self.queue[0].lchild = new_node
            # 判断是否有右孩子
            else:
                self.queue[0].rchild = new_node
                # 辅助队列出队
                self.queue.pop(0)

    def lev_order(self):
        """
        层序遍历需要借助辅助队列：也是广度优先遍历
        首先建立辅助队列
        根节点入队，用while来判断队列是否为空
        :return:
        """
        # 先建立辅助队列
        self.queue.clear()
        # 根节点入队
        self.queue.append(self.root)
        # 判断队首是否为空
        while self.queue:
            # 队首不为空，出队,获取当前节点
            node: Node = self.queue.pop(0)
            # 打印出队的元素
            print(node.value, end=' ')
            if node.lchild:
                self.queue.append(node.lchild)
            if node.rchild:
                self.queue.append(node.rchild)

    def pre_order(self, node: Node):
        """
        递归思想实现前序遍历：深度优先遍历
        :param node:
        :return:
        """
        if node:  # 防止空节点
            # 打印当前节点的值
            print(node.value, end=' ')
            # 递归左子树
            self.pre_order(node.lchild)
            # 递归右子树
            self.pre_order(node.rchild)

    def mid_order(self, node: Node):
        """
        递归思想实现中序遍历
        :param node:
        :return:
        """
        if node:
            self.mid_order(node.lchild)
            print(node.value, end=' ')
            self.mid_order(node.rchild)

    def end_order(self, node: Node):
        """
        递归思想实现后序遍历
        :param node:
        :return:
        """
        if node:
            self.end_order(node.lchild)
            self.end_order(node.rchild)
            print(node.value, end=' ')


if __name__ == '__main__':
    tree = Tree()
    # 层次建树
    for i in range(1, 11):
        tree.build_tree(i)
    # 前序遍历
    tree.pre_order(tree.root)
    print()
    # 中序遍历
    tree.mid_order(tree.root)
    print()
    # 后序遍历
    tree.end_order(tree.root)
    print()
    # 层序遍历
    tree.lev_order()
